#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <omp.h>

struct node {
	struct node *next;
	void *data;
};

struct queue {
	omp_lock_t lock;
	struct node *head;
	struct node *tail;
};

// append data to q->tail
void enqueue( struct queue *q, void *data ) {
	struct node *n;

	// prepare node
	n = malloc( sizeof(struct node) );
	n->data = data;
	n->next = NULL;

	// enqueue node

#pragma omp critical(tail)
{
	if( q->tail )
		q->tail->next = n;
	q->tail = n;
}
	// let head point to node if queue was empty
#pragma omp critical(tail)
{
	if( !q->head )
		q->head = q->tail;
}

}

// return q->head->data
void *dequeue( struct queue *q ) {
	void *data;
	struct node *n;


	// check for empty queue
	if( !q->head )
		return NULL;
#pragma omp critical(tail)
{
	// dequeue head node
	n = q->head;
	q->head = q->head->next;
}
	// don't let tail point to the dequeued node
#pragma omp critical(tail)
{
	if( !q->head )
		q->tail = NULL;
}

	// extract data and free node
	data = n->data;
	free(n);
	assert(data);

	return data;
}



int main( int argc, char **argv ) {
	struct queue q = { .head = NULL, .tail = NULL };

	#pragma omp parallel
	#pragma omp single nowait 
	{
		long i=0;
		for(i=1;i<3;++i) {
			#pragma omp task 
			{
				long j=0;
				for(j=0;j<20;++j) {
					enqueue(&q,(void*)(i*1000+j));
				}
			}
			#pragma omp task 
			{
				long d;
				long j=0;
				for(j=0;j<20;++j) {
					d = (long)dequeue(&q);
					if(d)
						printf("dequeue %ld\n",d);
				}
			}
		}
	}

	long d;
	while(1) {
		d = (long)dequeue(&q);
		if(!d)
			break;
		printf("dequeue outside %ld\n",d);
	}
	assert(!q.head && !q.tail);

	return 0;
}
